/*
 * frequent.cxx
 *
 *  Created on: 5:20:37 PM Nov 1, 2012
 *      Author: Pallab
 * "I have not failed, I have just found 10000 ways that won't work.
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait(double seconds) {
	double endtime = clock() + (seconds * CLOCKS_PER_SEC);
	while (clock() < endtime) {
		;
	}
}
#define T int
inline T fastIn() {
	register char c = 0;
	register T a = 0;
	bool neg = false;
	while (c < 33)
		c = getchar();
	while (c > 33) {
		if (c == '-') {
			neg = true;
		} else {
			a = (a * 10) + (c - '0');
		}
		c = getchar();
	}
	return neg ? -a : a;
}
inline int maxx(int p, int q) {
	return p > q ? p : q;
}
inline int maxx(int p, int q, int r) {
	return maxx(p, maxx(q, r));
}
inline int maxx(int p, int q, int r, int s) {
	return maxx(p, maxx(q, maxx(r, s)));
}
const int MX = 100000;
int numbers_count, query_count;
int numbers[MX];
struct segment {
	int numL, numR, cntL, cntR, bst;
	segment() {
		numL = numR = cntL = cntR = bst = 0;
	}
	segment(int val) {
		numL = numR = val, cntL = cntR = bst = 1;
	}
	segment(segment l, segment r) {
		numR=r.numR;
		cntR=r.cntR;
		if(l.numR==r.numR){
			cntR+=l.cntR;
		}

		numL=l.numL;
		cntL=l.cntL;
		if(l.numL==r.numL){
			cntL+=r.cntL;
		}
		bst=maxx(l.bst,r.bst);
		if(l.numR==r.numL){
			bst=max(bst,l.cntR+r.cntL);
		}
	}
	void print() {
		cout << "[ " << numL << ' ' << numR << " ] = " << cntL << ' ' << cntR
				<< " " << bst << "\n";
		puts("--------");
	}
};
segment t[MX * 4];
#define L(x) ( x << 1 )
#define R(x) ( 1+( x << 1 ) )
#define M(x,y) ( (x+y) >> 1 )
namespace DS {
inline segment combine(segment l, segment r) {
	return segment(l, r);
}
void build(int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = segment(numbers[tl]);
	} else {
		int tm = M(tl, tr);
		build(L(v), tl, tm);
		build(R(v), tm + 1, tr);
		t[v] = combine(t[L(v)], t[R(v)]);
	}
}

segment query(int v, int tl, int tr, int l, int r) {
	if (l == tl && tr == r)
		return t[v];
	int tm = M(tl,tr);
	if (r <= tm)
		return query(L(v), tl, tm, l, r);
	if (l > tm)
		return query(R(v), tm + 1, tr, l, r);
	return combine(query(L(v), tl, tm, l, tm),
			query(R(v), tm + 1, tr, tm + 1, r));
}
}
inline void read() {
	query_count = fastIn();
	fo(i,numbers_count)
		numbers[i] = fastIn();
}
inline void proc() {
	DS::build(1, 0, numbers_count - 1);
	int l, r;
	fo(i,query_count)
	{
		l = fastIn() - 1, r = fastIn() - 1;
		segment res = DS::query(1, 0, numbers_count - 1, l, r);
		cout << res.bst << '\n';
	}
}
int main() {
#if defined( xerxes_pc )
	if (!freopen("in1", "r", stdin))
		puts("error opening file in "), assert(0);
#endif
	while (scanf("%d",&numbers_count)==1) {
		if (numbers_count == 0)
			break;
		read();
		proc();
	}
	return 0;
}
